207 . NewWorld Online

Description

NewWorld Online 的魔寵系統就快要開放了！大家都迫不及待要收服可愛的小動物當成自己的夥伴。但是管理員們十分緊張，他們擔心會有許多人騎著烏龜飛來飛去，釀成危險的空中車禍，所以管理員們決定在一些景點之間建立好安全的通道。

$N$ $10^6$ $1$ $10^6$ 的正整數，每一種建材的數量都足夠建造任意條通道。每一條通道會用同一種建材連接兩個不同的景點，但是為了適應景點的地形，建材的強度必須是兩端景點地形的公因數。為了建造一個方便又安全的場景，管理員們希望任兩個景點都能互相到達，而且不要形成環狀的路徑，以免有玩家迷路。

管理員希望建造的通道能堅固一點，可是他們忙著看梅普露賣萌，沒空處理遊戲環境，所以決定找你幫忙。請你規劃一個蓋通道的方式，並告訴他們建材強度的總和最大可以有多少。

Input Format

$N$ $N$ $a_1,a_2,\ldots,a_n$ $i$ 個景點的地形。

$1\le N\le 10^5$
$1\le a_i \le 10^6$

Output Format

輸出一個正整數代表建材強度的總和的最大值。一種建材使用多次時強度也會以多倍計算。

Sample Input 1


xxxxxxxxxx
2
1
4
2
2 4 8 16

Sample Output 1


xxxxxxxxxx
1
1
14

Sample Input 2


xxxxxxxxxx
2
1
5
2
34 38 25 11 49

Sample Output 2


xxxxxxxxxx
1
1
5

Subtasks

No.	Testdata Range	Constraints	Score
1	0~1	範例測資	0
2	0~22	$N\le2000$	30
3	0~48	無其他限制	70

Testdata and Limits

No.	Time Limit (ms)	Memory Limit (VSS, KiB)	Output Limit (KiB)	Subtasks
0	4000	524288	65536	1 2 3
1	4000	524288	65536	1 2 3
2	4000	524288	65536	2 3
3	4000	524288	65536	2 3
4	4000	524288	65536	2 3
5	4000	524288	65536	2 3
6	4000	524288	65536	2 3
7	4000	524288	65536	2 3
8	4000	524288	65536	2 3
9	4000	524288	65536	2 3
10	4000	524288	65536	2 3
11	4000	524288	65536	2 3
12	4000	524288	65536	2 3
13	4000	524288	65536	2 3
14	4000	524288	65536	2 3
15	4000	524288	65536	2 3
16	4000	524288	65536	2 3
17	4000	524288	65536	2 3
18	4000	524288	65536	2 3
19	4000	524288	65536	2 3
20	4000	524288	65536	2 3
21	4000	524288	65536	2 3
22	4000	524288	65536	2 3
23	4000	524288	65536	3
24	4000	524288	65536	3
25	4000	524288	65536	3
26	4000	524288	65536	3
27	4000	524288	65536	3
28	4000	524288	65536	3
29	4000	524288	65536	3
30	4000	524288	65536	3
31	4000	524288	65536	3
32	4000	524288	65536	3
33	4000	524288	65536	3
34	4000	524288	65536	3
35	4000	524288	65536	3
36	4000	524288	65536	3
37	4000	524288	65536	3
38	4000	524288	65536	3
39	4000	524288	65536	3
40	4000	524288	65536	3
41	4000	524288	65536	3
42	4000	524288	65536	3
43	4000	524288	65536	3
44	4000	524288	65536	3
45	4000	524288	65536	3
46	4000	524288	65536	3
47	4000	524288	65536	3
48	4000	524288	65536	3